\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{listings}
\usepackage{indentfirst}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{dinossauro}
\renewcommand{\familydefault}{\sfdefault}
\renewcommand{\lstlistingname}{Listagem}
\usepackage[margin=2.5cm,noheadfoot]{geometry}

\begin{document}

\lstset{language=Java,
%extendedchars=\true,
%inputencoding=utf8
% literate={ó}{{\'o}}1
%            {á}{{\'a}}1
% 	   {é}{{\'e}}1
% 	   {í}{{\'i}}1
%            {ú}{{\'u}}1
% 	   {ã}{{\~a}}1
% 	   {õ}{{\~o}}1
% 	   {ç}{{\'c}}
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=1,                   % the step between two line-numbers. If it's 1 each line will be numbered
%numbersep=5pt,                  % how far the line-numbers are from the code
%backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
%showspaces=false,               % show spaces adding particular underscores
%showstringspaces=false,         % underline spaces within strings
%showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,	                % adds a frame around the code
tabsize=2,	                % sets default tabsize to 2 spaces
%captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
backgroundcolor=\color[rgb]{0.97,0.97,0.97},  % choose the background color. You must add \usepackage{color}
%breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
%title=\lstname,                 % show the filename of files included with \lstinputlisting; also try caption instead of title
%escapeinside={\%*}{*)}          % if you want to add a comment within your code
}

\include{capa}

\tableofcontents
\newpage

\section{Introdução}

O problema da mochila é um problema de otimização combinatorial classificado como NP-completo,
e pode ser definido como: dado um conjunto $C_{n}$ de $n$ ítens, representado por $C_{n}=\{1,2,...,n\}$,
onde cada item $I \in C_{n}$ tem peso $w_{i}$ e utilidade $p_{i} (w_{i}>0; p_{i}>0)$. Deseja-se determinar
um subconjunto $S$ dos ítens tal que a soma dos pesos dos elementos de $S$ seja menor ou igual à capacidade
da mochila $M$, e a utilidade total dos elementos de $S$ seja a maior possível.

O presente trabalho propõe o uso de um algoritmo evolucionário para resolver o problema da mochila, tendo
como principal objetivo entender e implementar seus componentes básicos, fazendo uma análise exaustiva dos
parâmetros utilizados e estudando como esses interferem no resultado obtido pelo AE.

Neste relatório serão explicados os detalhes de implementação e apresentados os resultados e análises dos experimentos efetuados.

\section{Implementação}

Utilizou-se a linguagem de programação Java para a implementação do algoritmo evolucionário.

\subsection{A estruturação das classes}

A estruturação do programa foi feita em quatro classes:

\begin{itemize}
\item Individuo - Classe responsável pelas funções de criação e acesso aos campos de um Individuo, cuja representação será explicada na seção seguinte.

\item Populacao - Classe responsável pelas funções de criação e acesso aos campos de uma População, que é um vetor de indivíduos.

\item Knapscack - Classe que implementa as funções principais do algoritmo evolucionário. Ela contém o método principal de resolução invocado no main, assim como os métodos de geração de uma população inicial, seleção, crossover e mutação, que ficarão mais claros adiante.

\item Main - Classe responsável por tratar os dados de entrada e saída e calcular as médias e desvios padrões
das estatísticas. Como se trata de um método estocástico, as estatísticas devem ser consideradas a partir das médias de pelo menos 30 execuções. Ao invés de rodar o programa 30 vezes para cada entrada, optou-se por efetuar um loop dentro da função main que invocasse a função principal de resolução do AE, de forma que assim já viabilizasse o processo de obtenção das médias e desvios padrões para a geração dos gráficos apresentados na seção de Experimentos.

\end{itemize}

\subsection{A representação do indivíduo}

Um indivíduo da população é representado como um vetor de identificadores, que corresponde ao conjunto de objetos (itens) que são selecionados para compor a mochila. A partir de cada identificador, pode-se facilmente verificar o valor da utilidade e do peso correspondentes. Essa abordagem por vetor de identificadores faz-se importante, uma vez que facilita as operações genéticas que serão explicadas posteriormente.

A fim de verificar se um indivíduo corresponde ou não a uma solução (a soma dos pesos de seus objetos não ultrapassa a capacidade da mochila) e medir a qualidade da possível solução, foi acrescentado no indivíduo um atributo para armazenar sua fitness.

\subsection{A fitness dos indivíduos}

A fitness de um indivíduo foi definida como sendo:

\begin{itemize}
\item a soma das utilidades dos objetos selecionados - para o caso em que a soma dos pesos não ultrapassa a capacidade da mochila e o indivíduo é uma possível solução para o problema;
\item - (menos) a soma dos pesos - para o caso em que a soma dos pesos ultrapassa a capacidade da mochila e o indivíduo não é uma possível solução para o problema;  
\end{itemize}

Essa separação das fitness conforme a possibilidade ou não de um indivíduo ser uma solução é importante, pois permite inserir na população apenas indivíduos "válidos", que podem ser uma solução para o problema.

Quando um indivíduo é criado, sua fitness é inicializada como $-1$, o que corresponde a um indivíduo que ainda não possui objetos selecionados.

\subsection{A geração da população inicial}

A população inicial é gerada aleatoriamente. A partir do tamanho da população $t$, que é passado como parâmetro, são gerados $t$ indivíduos. Para cada um, são selecionados objetos de forma aleatória. Faz-se isso até que se exceda a capacidade de sua mochila, retirando-se então o último objeto selecionado e obtendo um indivíduo "válido" para ser inserido na população.

\subsection{A seleção dos indivíduos}

A seleção dos indivíduos foi feita com base em uma seleção por torneios de tamanho $k$, passado como parâmetro.
Dessa forma, selecionam-se $k$ indivíduos aleatoriamente e verifica-se qual é o melhor indivíduo entre eles, o qual será escolhido.

São selecionados dois indivíduos para passarem pelas operações genéticas de crossover e mutação (condicionados por suas probabilidades) e, assim, propiciarem a origem de novos indivíduos para a próxima geração. O processo de seleção de dois pais e realização das operações genéticas é feito até que o tamanho da população $t$ da nova geração seja atingido, quando a população velha é substituída pela nova e um novo ciclo se inicia.

\subsection{Os operadores genéticos}

Dois operadores genéticos foram utilizados: crossover e mutação.

\subsubsection{Crossover}

A partir de dois indivíduos pais, geram-se dois indivíduos filhos diferentes, formados a partir de uma troca de subconjuntos de objetos.

O crossover é feito da seguinte maneira:

\begin{enumerate}
\item Escolhe-se aleatoriamente uma posição no vetor de identificadores (objetos) de um indivíduo pai, partindo o conjunto em dois subconjuntos;
\item Escolhe-se aleatoriamente uma posição no vetor de identificadores (objetos) do outro indivíduo pai, partindo o conjunto em dois subconjuntos;
\item Ao final de 1 e 2, cada indivíduo terá duas partes $p_{1}$ e $p_{2}$. As segundas partes $p_{2}$ dos indivíduos são trocadas entre eles, resultando em filhos diferentes.
\end{enumerate}

Um exemplo de crossover entre os pais: $I_{1}\{2, 6, 8, 76\}$ e $I_{2}\{52, 60, 1, 100\}$, que escolhe para ambos a posição $2$ (metade do conjunto), resultaria nos filhos: $I_{3}\{2, 6, 1, 100\}$ e $I_{4}\{52, 60, 8, 76\}$.

Uma consideração importante é que quando o crossover é escolhido para ser efetuado em função de sua probabilidade, este é feito até que pelo menos um filho seja considerado válido (a soma dos pesos dos objetos não excede a capacidade da mochila) para ser inserido na população da próxima geração.

\subsubsection{Mutação}

A mutação é feita individualmente em cada um dos dois indivíduos selecionados, sendo condicionada a uma probabilidade.

A partir do número de objetos de cada indivíduo, selecionam-se aleatoriamente $x$ posições a serem trocadas por outros objetos, também selecionados de forma aleatória. O número $x$ de posições a serem trocadas é dado pelo teto da multiplicação $0.03 \times tam$, onde $tam$ é o tamanho do conjunto de objetos do indivíduo e o valor $0.03$ foi escolhido arbitrariamente. Dessa forma, sempre que ocorre uma mutação, pelo menos um objeto é mutado.

Assim como no crossover, quando a mutação é escolhida para ser efetuada em função de sua probabilidade, esta é feita até que se tenham indivíduos "válidos" para serem inseridos na próxima geração.

\section{Compilação e execução}

Para compilar e executar o programa, pode-se usar o script "experimentos.sh" contido na pasta "resultados", que efetua automaticamente diversos experimentos usando os arquivos de entrada disponibilizados no site da disciplina.

Caso se deseje compilar o programa manualmente, execute o comando $javac -cp <classpath> <source>/*.java$ na linha de comando, onde $<classpath>$ é o diretório "bin" e $<source>$ é o diretório "src".

Para executá-lo manualmente, execute o comando $java -cp <classpath> Main -t <parametro1> -g <parametro2> -k <parametro3> -c <parametro4> -m <parametro5> -e <parametro6> -r <parametro7> -i <parametro8> -o <parametro9>$, onde $<classpath>$ é o diretório "bin" e os parâmetros de entrada são explicados abaixo:

\begin{itemize}
\item $parametro1$ - tamanho da população;
\item $parametro2$ - número de gerações;
\item $parametro3$ - tamanho do torneio para a seleção;
\item $parametro4$ - probabilidade de crossover (0.0 a 1.0);
\item $parametro5$ - probabilidade de mutação (0.0 a 1.0);
\item $parametro6$ - sem ou com elitismo (0 ou 1, respectivamente);
\item $parametro7$ - sem ou com repetição de indivíduos na população (0 ou 1, respectivamente);
\item $parametro8$ - arquivo de entrada, no formato dos .dat disponibilizados no site da disciplina;
\item $parametro9$ - arquivo de saída, no qual serão impressas as estatísticas para análise;
\end{itemize}

Caso não se forneça algum parâmetro de entrada, há parâmetros default definidos no Main para propiciar a execução correta do AE.




\section{Experimentos}

Foram feitos experimentos para quatro instâncias do problema da mochila, sendo duas delas detalhadas (uma com 300 objetos e outra com 500, ambas com a capacidade da mochila em 10\% do peso total). Para cada instância, os parâmetros foram variados como descrito na especificação deste trabalho, e os resultados são analisados na sequência. Em todas as análises, são consideradas seis características principais: melhor fitness, pior fitness, fitness média, número de indivíduos repetidos, número de indivíduos gerados por crossover cuja fitness é melhor que a média das fitness dos pais e número de indivíduos gerados por crossover cuja fitness é pior que a média das fitness dos pais.

\subsection{Variação do tamanho da população}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010PFitness.png}
    \caption{\small Instância com 300 objetos}
    \label{infoGeral}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010PFitness.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\newpage

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010PIndividuos.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010PIndividuos.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

Quanto às características relacionadas à fitness, a variação do tamanho da população para as duas instâncias do problema (com 300 e 500 objetos) gerou resultados semelhantes. Em ambos os casos, os valores de melhor fitness e fitness média aumentam à medida que o tamanho da população aumenta porque quanto maior é a população, maiores as chances de aparecerem indivíduos com melhores fitness, pois os operadores genéticos serão aplicados mais vezes em cada geração. Da mesma forma, as chances de aparecerem indivíduos piores também são maiores com o aumento da população, porque os operadores genéticos são aplicados mais vezes a cada geração.

Em relação às características relacionadas ao número de indivíduos, novamente o comportamento é muito semelhante para as duas instâncias do problema. Quanto maior a população, maior a chance de ser gerado um indivíduo repetido, pois maior é a quantidade de indivíduos que podem ser gerados novamente. Da mesma forma, a quantidade de indivíduos melhores ou piores que os pais gerados pro crossover é maior, pois há maior chance de se ter maior variabilidade na população, o que faz com que se tenha maior chance de geração de indivíduos melhores ou piores que os pais.

\subsection{Variação do número de gerações}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010GFitness.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010GFitness.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010GIndividuos.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010GIndividuos.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

Foram efetuados testes considerando o número de gerações 30, 50 e 100 para duas instâncias do problema contendo 300 e 500 objetos.

Analisando-se os gráficos da variação das fitness em função do aumento do número de gerações, percebe-se que tanto para 300 quanto para 500 objetos, seus valores sofrem pouca variação quando se aumenta o número de gerações.

Para o problema com 300 objetos, há um pequeno aumento da fitness média e da melhor fitness, acompanhado de uma pequena redução da pior fitness. Essa pequena variação mostra claramente que para 30 gerações, o algoritmo já está convergindo. O melhor caso se dá para 100 gerações, pouco acima do pior caso. O aumento do número de objetos não interfere muito no comportamento das fitness. Uma diferença interessante é que para 500 objetos, o algoritmo encontra a melhor solução com 50 gerações, e a partir de então, tem um leve declínio.

Com relação às características relacionadas ao número de indivíduos, percebe-se que o comportamento é o mesmo tanto para o problema com 300 objetos quanto para o de 500.

O número de indivíduos repetidos cresce em função do aumento do número de gerações. Isso se deve ao fato de que, com o uso de elitismo e de uma seleção que privilegia o melhor indivíduo entre $k$ selecionados, quando não é feita uma operação genética em função de suas probabilidades associadas, a tendência de ocorrer repetição de bons indivíduos que ganham os torneios para se propagarem para as próximas gerações é maior.

Percebe-se também que o número de indivíduos gerados por crossover piores que os pais é maior que o número de indivíduos melhores. Isso se deve ao fato de que, com a pressão seletiva e o uso de elitismo, com o aumento do número de gerações, a população vai ficando "melhor", o que faz com que a chance de gerar um indivíduo melhor aleatoriamente por crossover seja menor do que a chance de gerar um pior.

\subsection{Variação da probabilidade de crossover}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010CFitness.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010CFitness.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010CIndividuos.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010CIndividuos.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

Novamente, o comportamento de todas as características é semelhante em ambas as instâncias do problema. Ao analisar os quatro gráficos em conjunto, pode-se perceber que o aumento da probabilidade de ocorrência de crossover diminui o número de indivíduos repetidos, devido ao aumento da variabilidade genética da população. Pode-se notar também que tanto o número de indivíduos piores quanto o de indivíduos piores que os pais gerados pro crossover aumenta, sendo que o número de indivíduos piores é  sempre maior. A explicação para isso está relacionada ao fato de os testes terem utilizado elitismo, já que o melhor indivíduo de cada geração é adicionado automaticamente à geração seguinte. Isso faz com que, à medida que se passam as gerações, a população possua mais indivíduos com boas fitness, o que dificulta a gereação de indivíduos melhores que eles.

Além disso, o fato de se gerar mais indivíduos piores que os pais faz a fitness média da população cair, como pode-se observar nos gráficos relacionados à fitness. Ainda assim, como a variabilidade genética é maior, a chance de se obter indivíduos melhores que os pais também é maior, o que é ilustrado pela curva de melhores fitness.

\subsection{Variação da probabilidade de mutação}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010MFitness.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010MFitness.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/300M010MIndividuos.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/experimento/500M010MIndividuos.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

Foram efetuados testes considerando a probabilidade de mutação 0.001 e 0.01 para duas instâncias do problema contendo 300 e 500 objetos.

Analisando-se os gráficos da variação das fitness em função do aumento da probabilidade de mutação, percebe-se que tanto para 300 quanto para 500 objetos, seus valores sofrem um pequeno aumento quando se aumenta a probabilidade de mutação.

O aumento das fitness é pequeno porque a probabilidade de mutação é pequena mesmo no maior caso (0.01), o que faz com que o efeito de sua mudança seja menor. No entanto, o aumento da fitness média da população comprova a importância da aleatoriedade para a diversidade da população, o que está diretamente relacionado com sua qualidade, uma vez que aumenta-se a chance de haver indíviduos melhores em função da variabilidade genética, os quais são propagados por elitismo e pressão seletiva.

Com relação às características relacionadas ao número de indivíduos, percebe-se que o comportamento é o mesmo tanto para o problema com 300 objetos quanto para o de 500.

O número de indivíduos repetidos diminui com o aumento da probabilidade de mutação. Isso era esperado, uma vez que a mutação faz com que aumente a variabilidade genética, o que consequentemente gera mais indivíduos distintos. O declínio suave do gráfico é em função da probabilidade de mutação ser pequena mesmo no maior caso (0.01), conforme já explicado.

O número de indivíduos gerados por crossover piores ou melhores que os pais é praticamente constante, o que era esperado, uma vez que a mutação é independente do crossover. Uma pequena variação é explicada em função da execução do crossover ser condicionada a uma probabilidade, sendo não-determinística.

\subsection{Variação do tamanho do torneio}

Nesses experimentos, os valores dos parâmetros mantidos fixos são:
\begin{itemize}
 \item Tamanho da população: 50
 \item Número de gerações: 50
 \item Probabilidade de crossover: 0.6
 \item Probabilidade de mutação: 0.001
 \item Elitismo: sim
\end{itemize}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/300M010K2Fitness.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/300M010K5Fitness.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/300M010K2Individuos.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/300M010K5Individuos.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/500M010K2Fitness.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/500M010K5Fitness.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}

\begin{figure}[ht!]
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/500M010K2Individuos.png}
    \caption{\small Instância com 300 objetos}
  \end{minipage}
  \begin{minipage}[b]{0.48 \linewidth}
    \centering
    \includegraphics[scale=0.35]{../resultados/graficos/geracao/500M010K5Individuos.png}
    \caption{\small Instância com 500 objetos}
  \end{minipage}
\end{figure}


Pela análise dos gráficos pode-se notar que os resultados foram semelhantes para as instâncias do problema contendo 300 e 500 objetos.

No caso das características relacionadas à fitness, percebe-se que em todos os casos o comportamento é semelhante, com os valores de melhor fitness e fitness média aumentando e convergindo, enquanto o valor da pior fitness vai decrescendo ao longo das gerações. Isso é esperado porque, utilizando-se elitismo, os melhores indivíduos de cada geração são adicionados à nova população, o que faz com a fitness média aumente uma vez que o número de indivíduos com boas fitness vai se tornando bem maior que o de indivíduos com fitness baixa. Além disso, à medida que a população vai evoluindo (indivíduos vão sendo submetidos a crossover e mutação), espera-se gerar novos indivíduos cujas fitness serão melhores ou piores que os já presentes na população.

Entretanto, pode-se notar que, para $K = 5$, os valores de fitness tendem a convergir mais rapidamente e para valores menores que os observados nos casos em que $K = 2$. Isso pode ser explicado pela maior pressão seletiva obtida para maiores valores de $K$, pois quanto maior o número de participantes do torneio, maior a chance de o melhor indivíduo dentre os participantes ser o melhor da população, o que faz com que as melhores fitness sejam encontradas mais rapidamente e a convergência seja mais rápida.

Em relação às características relacionadas ao número de indivíduos, novamente os resultados são muito semelhantes para ambas as instâncais do problema. Em todos os casos, percebe-se que o número de indivíduos repetidos aumenta ao longo das gerações, enquanto o número de indivíduos melhores e piores gerados por crossover aumentam inicialmente, mas depois passam a decrescer. Esse comportamento é esperado porque a contagem do número de indivíduos repetidos é feita somando o número de indivíduos repetidos em cada geração. À medida que se passam as gerações, a tendência desse número é só aumentar. Já no caso dos indivíduos gerados por crossover, à medida que se passam as gerações, os melhores indivíduos vão se aproximando da solução e os piores indivíduos vão se tornando ainda piores, o que torna mais difícil a geração de indivíduos melhores ou piores que os pais pro crossover (pois os pais já são muito bons ou muito ruins).

Nota-se, ainda, que para $K = 5$ o número de indivíduos repetidos tende a convergir mais rapidamente, assim como o número de indivíduos melhores e piores que os pais tende a diminuir mais rapidamente. Isso pode ser explicado pela maior pressão seletiva, que faz com que os melhores indivíduos sejam encontrados mais rapidamente (dificultando a geração de indivíduos melhores por crossover) e faz com que o número de indivíduos repetidos convirja mais rapidamente justamente devido à convergência mais rápida da população.

\subsection{Elitismo}

Seguem abaixo as estatísticas finais da execução do Algoritmo Genético com os melhores parâmetros, com e sem elitismo. Os melhores parâmetros são:

\begin{itemize}
\item Tamanho da população: 100
\item Número de gerações: 100
\item Tamanho $k$ do torneio: 5
\item Probabilidade de crossover: 0.95
\item Probabilidade de mutação: 0.01
\end{itemize}

\begin{codigoMargem}
Melhor configuração, arquivo com 300 objetos e capacidade da mochila em de 10\%, 
com elitismo

Média das melhores fitness: 38992.0
Média das piores fitness: 4211.0
Média das fitness médias: 33159.25579970207
Média dos números de indivíduos repetidos: 49.0
Média dos números de indivíduos gerados por crossover que são melhores 
que os pais: 5.0
Média dos números de indivíduos gerados por crossover que são piores 
que os pais: 51.0
Desvio padrão das melhores fitness: 2545.0843763534876
Desvio padrão das piores fitness: 3046.091814904401
Desvio padrão das fitness médias: 2348.2550162056564
Desvio padrão dos números de indivíduos repetidos: 3.4987682561645643
Desvio padrão dos números de indivíduos gerados por crossover que são melhores 
que os pais: 6.443387414963525
Desvio padrão dos números de indivíduos gerados por crossover que são piores 
que os pais: 5.17287354278598

Melhor configuração, arquivo com 300 objetos e capacidade da mochila em de 10\%, 
sem elitismo

Média das melhores fitness: 40622.0
Média das piores fitness: 5813.0
Média das fitness médias: 34531.10020382443
Média dos números de indivíduos repetidos: 46.0
Média dos números de indivíduos gerados por crossover que são melhores 
que os pais: 8.0
Média dos números de indivíduos gerados por crossover que são piores 
que os pais: 55.0
Desvio padrão das melhores fitness: 2275.1750519995994
Desvio padrão das piores fitness: 3303.5838376547663
Desvio padrão das fitness médias: 2280.2727815140893
Desvio padrão dos números de indivíduos repetidos: 4.185360364330692
Desvio padrão dos números de indivíduos gerados por crossover que são melhores 
que os pais: 7.423169691975394
Desvio padrão dos números de indivíduos gerados por crossover que são piores 
que os pais: 6.948083337796512

Melhor configuração, arquivo com 500 objetos e capacidade da mochila em de 10\%, 
com elitismo

Média das melhores fitness: 55110.0
Média das piores fitness: 8757.0
Média das fitness médias: 47499.964678694334
Média dos números de indivíduos repetidos: 46.0
Média dos números de indivíduos gerados por crossover que são melhores 
que os pais: 10.0
Média dos números de indivíduos gerados por crossover que são piores 
que os pais: 56.0
Desvio padrão das melhores fitness: 3213.9349498813704
Desvio padrão das piores fitness: 5564.949970342393
Desvio padrão das fitness médias: 3191.586594171261
Desvio padrão dos números de indivíduos repetidos: 4.777822328937792
Desvio padrão dos números de indivíduos gerados por crossover que são melhores 
que os pais: 8.147349897041835
Desvio padrão dos números de indivíduos gerados por crossover que são piores 
que os pais: 7.845490688155269
\end{codigoMargem}

\begin{codigoMargem}
Melhor configuração, arquivo com 500 objetos e capacidade da mochila em de 10\%, 
sem elitismo

Média das melhores fitness: 56102.0
Média das piores fitness: 7032.0
Média das fitness médias: 47995.425845836406
Média dos números de indivíduos repetidos: 45.0
Média dos números de indivíduos gerados por crossover que são melhores 
que os pais: 8.0
Média dos números de indivíduos gerados por crossover que são piores 
que os pais: 54.0
Desvio padrão das melhores fitness: 3192.108313130778
Desvio padrão das piores fitness: 5117.959951871988
Desvio padrão das fitness médias: 3504.493058397044
Desvio padrão dos números de indivíduos repetidos: 7.26825881534887
Desvio padrão dos números de indivíduos gerados por crossover que são melhores 
que os pais: 7.869627340780415
Desvio padrão dos números de indivíduos gerados por crossover que são piores 
que os pais: 7.317904354248628
\end{codigoMargem}

Observando-se os dados acima é possível observar que a utilizaçõa de elitismo diminui um pouco a média das melhores fitness, o que pode estar relacionado com uma convergência prematura para mínimos locais, no caso desse problema. Ainda assim, os resultados não foram tão diferentes, o que significa que esse parâmetro não afeta tanto nos resultados do algoritmo genético aplicado à resolução do problema da mochila

\section{Conclusões}

O desenvolvimento desse trabalho e as análises feitas sobre os resultados mostraram que a configuração dos parâmetros é muito importante para algoritmos evolucionários. Sendo assim, uma análise minuciosa dos resultados faz-se importante para que se possa selecionar os melhores parâmetros, levando sempre em consideração o caráter estocástico do algoritmo.

Os resultados obtidos mostraram que se pode usar algoritmos evolucionários como soluções alternativas para problemas NP-completo. Apesar de ser um método estocástico, ele sempre apresenta uma solução boa, principalmente com uma escolha adequada dos parâmetros.

Com base nos gráficos apresentados, concluímos que a melhor configuração de parâmetros testados corresponde a:

\begin{itemize}
\item Tamanho da população: 100
\item Número de gerações: 100
\item Tamanho $k$ do torneio: 5
\item Probabilidade de crossover: 0.95
\item Probabilidade de mutação: 0.01
\item Elitismo: não
\end{itemize}

Com nossos objetivos atingidos, concluímos a realização do trabalho.

\newpage
\appendix

\section{Médias e Desvios Padrões}

Todos os resultados obtidos e apresentados no documento acima foram feitos com base em 30 execuções de cada experimento. Segue abaixo as médias das características mais importantes com seus respectivos desvios padrões.

\lstinputlisting[caption=Médias e Desvios padrões]{../resultados/mediasExecucoes.txt}


\nocite{*}
\bibliographystyle{plain}
\bibliographystyle{apalike}
\renewcommand{\refname}{Referências}
\addcontentsline{toc}{section}{Referências}
\bibliography{referencias}

\end{document}
